/*
 * @lc app=leetcode.cn id=329 lang=golang
 *
 * [329] 矩阵中的最长递增路径
 */

// @lc code=start

// 使用深度优先遍历对于路径进行遍历
// 但是，在遍历过程中，我们可以发现，每个点的最长递增路径是唯一的
// 因此，我们可以在深度优先遍历中的途中，记录每个点的最长递增路径
// 如果遍历到该点，可以直接返回记录中的值，不需要再次进行计算，避免了重复计算
func longestIncreasingPath(matrix [][]int) int {
	m, n := len(matrix), len(matrix[0])
	visit := make([][]int, m)
	for i, _ := range visit {
		visit[i] = make([]int, n)
	}
	maxLen := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if visit[i][j] == 0 {
				tmp := dfs(&matrix, &visit, i, j, m, n, -1)
				if tmp > maxLen {
					maxLen = tmp
				}
			} else {
				if visit[i][j] > maxLen {
					maxLen = visit[i][j]
				}
			}
		}
	}
	// fmt.Println(visit)
	return maxLen
}

func dfs(matrix, visit *[][]int, i, j, m, n, tmp int) int {
	if i < 0 || i >= m || j < 0 || j >= n {
		return 0
	}
	if (*visit)[i][j] != 0 && (*matrix)[i][j] > tmp {
		return (*visit)[i][j]
	}
	if (*matrix)[i][j] > tmp {
		tmp = (*matrix)[i][j]
		left := dfs(matrix, visit, i-1, j, m, n, tmp)
		right := dfs(matrix, visit, i+1, j, m, n, tmp)
		up := dfs(matrix, visit, i, j-1, m, n, tmp)
		down := dfs(matrix, visit, i, j+1, m, n, tmp)
		(*visit)[i][j] = 1 + max(max(left, right), max(up, down))
		return (*visit)[i][j]
	}
	return 0
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

// @lc code=end
